#include <bits/stdc++.h>
using namespace std;
//二分查找target在数组中的插入位置
//1.注意当前插入的值是否在数组中存在，不存在要返回它将要插入的位置，存在返回和他相同的值的左边的位置
//2.注意边界情况，当循环结束时，它是否比当前查找到的值大或者小，根据判断返回left or left-1
// class Solution {
//     public:
//         int searchInsert(vector<int>& nums, int target) {
//             int left=0,right=nums.size()-1;
//             while(left<right)
//             {
//                 int mid=left+(right-left)/2;
//                 if(nums[mid]==target)return mid;
//                 else if(nums[mid]<target)left=mid+1;
//                 else right=mid-1;
//             }
//             if(target>nums[left])return left+1;
//             return left; 
//         }
//     };

//查找将数组分成两个区间的数的下标，左边比这个数小，右边也比这个数小
//1.刚开始踩坑了，看着是二分没想到怎么用，写了两次超时，去判断mid和左右的大小关系了
//2.二段性，这个数存在的话，它的右边一定是比左边小的，根据左边来判断是没有意义的，
//  可能左边的右边还有比左边的右边这个数大的{left,right,left的right}类似这种，left<right但是right<left的right
//3.出现2这种情况，让left接着走到mid的位置，毕竟2可能不会出现，走到mid+1就超错过了
//4.有时二分并不直接需要用到left和right位置的值，最核心的是利用它们的下标来确定mid，只要能控制好left和right，就一定能做对题
// class Solution {
//     public:
//         int peakIndexInMountainArray(vector<int>& nums) {
//             int left=0,right=nums.size()-1;
//             while(left<right)
//             {
//                 int mid=left+(right-left+1)/2;
//                 // if(nums[mid]>nums[mid+1])right=mid;
//                 // else left=mid+1;
//                 if(nums[mid]<nums[mid-1])right=mid-1;
//                 else left=mid;//这种写法将(right-left)/2;换成(right-left+1)/2;
//             }
//             return left;
//         }
//     };

//这个题目将数组经过n次旋转后，将数组分成了两个递增的区间[3,4,5,6,1,2,3]
//1.没想到怎么找二段性，看了一下题解，是类似反比例函数的图像，可以将旋转后的数组分成两部分
// [大于nums.back()] [小于等于nums.back()],这样就找到二段性了
//2.使用nums.front()做参照物也可以解决，我能想到的就只有特判了，判断一下头和尾谁大谁小
// class Solution {
//     public:
//         int findMin(vector<int>& nums) {
//             int left = 0, right = nums.size() - 1;
//             int n = nums.size();
//             while(left < right)
//             {
//                 int mid = left + (right - left) / 2;
//                 if(nums[mid] > nums[n - 1])left = mid + 1;
//                 else right = mid;
//             }
//             return nums[left];
//         }
//     };

// class Solution 
// {
//     public:
//         int findMin(vector<int>& nums) 
//         {
//             int left = 0, right = nums.size() - 1;
//             while(left < right)
//             {
//                 int mid = left + (right - left)/2;
//                 if(nums[mid] >= nums.front())left = mid + 1;
//                 else right = mid; 
//             }
//             return nums[left];
//         }
// };

//https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/
//仅有一位同学缺席，当有一位同学缺席时，从缺席的位置开始后面一定时没有能匹配上的
//刚开始的时候只看到了一位同学缺席，没想到后面还有人，导致没想到怎么划分二段性
//还有一个坑就是right怎么变化，如果缺席的同学后只有一位同学的话，让他等于mid是正确的，
//但是当后面有很多同学时，就不对了，不动right的位置会导致满足条件后，left无法移动，就造成死循环了
//因为前者是一个一个走过去的，他的前面不会有缺席的，

//反思：1.不能只看题目给的样例，自己多写几个看看
//     2.还是没有理解left和right只是控制循环是否进行的手段，最重要的是找到二段性和分析满足条件
//       后left和right如何变化
class Solution {
    public:
        int takeAttendance(vector<int>& records) {
            // int left=0, right = records.size() - 1;
            // while(left <= right)
            // {
            //     int mid = left + (right - left) / 2;
            //     if(records[mid] != mid)right = mid - 1;
            //     else left = mid + 1;
            // }
            // return left;
            int count=0,sum=0;
            for(int i=0;i<records.size()+1;i++)count+=i;
            for(int i=0;i<records.size();i++)sum+=records[i];
            return count-sum;
        }
    };